package com.desin.modle.datastruct.algo.sorts13;

public class MyBucketSort {
    /**
     *
     * @param arr 数据数组
     * @param bucketSize 单个桶的容量
     */
    public void bucketSort(int[] arr,int bucketSize){
        int min = arr[0];
        int max = arr[0];
        int length = arr.length;
        for(int i=0;i<length;i++){
            if(arr[i]<min){
                min=arr[i];
            }else if(arr[i]>max){
                max=arr[i];
            }
        }

        int bucketCount=(max-min)/bucketSize+1;
        int[][] buckets=new int[bucketCount][bucketSize];
        int[] bucketIndexs=new int[bucketCount];

        for(int i=0;i<length;i++){
            int bucketIndex = (arr[i] - min) / bucketSize;
            if(bucketIndexs[bucketIndex]==buckets[bucketIndex].length){
                //todo 扩容
                kuorong(buckets,bucketIndex);
            }
            buckets[bucketIndex][bucketIndexs[bucketIndex]] = arr[i];
            bucketIndexs[bucketIndex] = bucketIndexs[bucketIndex]+1;
        }
        int k=0;
        for(int i=0;i<buckets.length;i++){
            if(bucketIndexs[i]==0){
                continue;
            }
            quickSort(buckets[i],0,bucketIndexs[i]-1);
            for(int j=0;j<bucketIndexs[i];j++){
                arr[k] = buckets[i][j];
                k++;
            }
        }
    }

    private void kuorong(int[][] buckets, int bucketIndex) {
        int[] bucket = buckets[bucketIndex];
        int[] newBucket = new int[2*bucket.length];
        for(int i=0;i<bucket.length;i++){
            newBucket[i]=bucket[i];
        }
        buckets[bucketIndex]=newBucket;
    }

    private void quickSort(int[] bucket, int start, int end) {
        int point = findPoint(bucket,start,end);
        quickSort(bucket,start,point-1);
        quickSort(bucket,point+1,end);
    }

    private int findPoint(int[] bucket, int start, int end) {
        int i=0;
        int point = bucket[end];
        for(int j=start;j<end;j++){
            if(bucket[j]<point){
                int temp = bucket[i];
                bucket[i]=bucket[j];
                bucket[j]=temp;
                i++;
            }
        }
        int temp = bucket[i];
        bucket[i]=point;
        bucket[end]=temp;
        return i;
    }
}
